#include "graph.h"
#include<bits/stdc++.h>
using namespace std;
const int MAXN=200+5;
mt19937 Rand(time(0));
int M,dis[MAXN][MAXN];
int deg[MAXN],fa[MAXN],to[MAXN][MAXN],n;
bool ok[MAXN][MAXN][MAXN];int tag[MAXN][MAXN],num[MAXN][MAXN];
vector<int> G[MAXN][MAXN][2][2];
bool c1[MAXN][MAXN],c2[MAXN][MAXN];
void dfs(int u) {
	deg[u]=NumberOfRoads();
	M+=deg[u],fa[u]=LastRoad();
	int col=Rand()%2+2;
	for(int i=1;i<=deg[u];++i) {
		if(i!=fa[u]) {
			Move(i,col);
			if(Color()>1) {
				tag[u][i]=LastRoad();
				c1[u][i]=col-1,c2[u][i]=Color()-1;
				G[i][LastRoad()][c1[u][i]][c2[u][i]].emplace_back(u);
				Move(LastRoad(),Color());
				continue;
			}
			++n;
			to[u][i]=n;
			dis[u][n]=dis[n][u]=1;
			dfs(n);
		}
	}
	if(~fa[u]) Move(fa[u],col);
}
int col[MAXN],Col[MAXN][MAXN];
bool jqh[MAXN][MAXN];
void bfs(int u) {
	col[u]=Rand()%3+1;
	for(int i=1;i<=deg[u];++i) {
		if(i!=fa[u]&&!tag[u][i]) {
			Move(i,col[u]);
			bfs(to[u][i]);
		}
	}
	if(~fa[u]) Move(fa[u],col[u]);
}
void cfs(int u) {
	for(int i=1;i<=deg[u];++i) {
		if(i!=fa[u]&&!tag[u][i]) {
			Move(i,col[u]);
			cfs(to[u][i]);
		}
		if(tag[u][i]&&!jqh[u][i]) {
			Move(i,col[u]);
			Col[u][i]=Color();
			Move(tag[u][i],Col[u][i]);
		}
	}
	if(~fa[u]) Move(fa[u],col[u]);
}
void solve() {
	bfs(1),cfs(1);
	for(int i=1;i<=n;++i) {
    	for(int j=1;j<=deg[i];++j) {
    		if(tag[i][j]) {
    			for(int k=1;k<=n;++k) {
    				if(ok[i][j][k]) {
    					if(col[k]!=Col[i][j]||col[i]!=Col[k][tag[i][j]]) {
    						ok[i][j][k]=ok[k][tag[i][j]][i]=0;
    						--num[i][j],--num[k][tag[i][j]];
						}
					}
				}
			}
		}
	}
}
void clear(int i,int j,int k) {
	jqh[i][j]=jqh[k][tag[i][j]]=1,dis[i][k]=dis[k][i]=1;
	for(int t=1;t<=n;++t) {
		if(t!=i&&ok[k][tag[i][j]][t]) {
			ok[t][tag[k][tag[i][j]]][k]=0;
			--num[t][tag[k][tag[i][j]]];
			if(num[t][tag[k][tag[i][j]]]==1) {
				for(int l=1;l<=n;++l) {
					if(ok[t][tag[k][tag[i][j]]]) {
						clear(t,tag[k][tag[i][j]],l);
						break;
					}
				}
			}
		}
	}
}
int sum[MAXN];
void Inspect(int R) {
    dfs(n=1);
    for(int i=1;i<=n;++i) {
    	for(int j=1;j<=deg[i];++j) {
    		if(tag[i][j]) {
    			for(auto k:G[tag[i][j]][j][c2[i][j]][c1[i][j]]) {
    				if(k!=i) ok[i][j][k]=1,++num[i][j];
				}
			}
		}
	}
	while(1) {
		bool flag=0;
		for(int i=1;i<=n;++i) {
			for(int j=1;j<=deg[i];++j) {
				if(tag[i][j]&&!jqh[i][j]) {
					if(num[i][j]>1) {
						flag=1;
						continue;
					}
					for(int k=1;k<=n;++k) {
						if(ok[i][j][k]) {
							clear(i,j,k);
							break;
						}
					}
				}
			}
		}
		if(!flag) break;
		solve();	
	}
	for(int i=1;i<=n;++i) {
		for(int j=1;j<=n;++j) {
			if(i==j) continue;
			if(!dis[i][j]) dis[i][j]=1e9;
		}
	}
	for(int k=1;k<=n;++k) {
		for(int i=1;i<=n;++i) {
			for(int j=1;j<=n;++j) {
				dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
			}
		}
	}
	for(int i=1;i<=n;++i) {
		for(int j=i+1;j<=n;++j) {
			++sum[dis[i][j]];	
		}
	}
	for(int i=1;i<=R;++i) Answer(i,sum[i]);
}
